import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Queue;

public class TestHeap {
    public int[] elem;
    public int usedSize;

    public TestHeap() {
        this.elem = new int[10];
    }

    //初始化数组
    public void initElem(int[] array) {
        for (int i = 0; i < array.length; i++) {
            elem[i] = array[i];
            usedSize++;
        }
    }

    //创建堆
    public void createHeap() {
        //确定每颗子树的父亲节点，一棵子树创建成堆之后，再重新向下调整另一颗子树
        for (int parent = (usedSize - 1 - 1) / 2; parent >= 0; parent--) {//这里从最后一位数组元素开始，找其结点，找父节点的公式为（i-1）/2,usedSize记录数组中的元素，所以数组最后一个元素为usedSize-1
            shiftDown(parent,usedSize);//将usedSize作为结束条件，每个父亲结点的孩子结点的下标都不可能超过数组的长度。如果再向下调整，一定会超过数组长度，结束调整。
        }
    }

    //向下调整，传父亲结点的下标，和每课树的结束下标
    private void shiftDown(int parent, int len) {
        int child = 2 * parent + 1;
        //最起码 要有左孩子，左孩子结点下标小于数组长度
        while (child < len) {
            //一定是有右孩子的情况，这样才能找到左右孩子结点的最大值。
            if (child + 1 < len && elem[child] < elem[child + 1]) {//如果右孩子结点大于左孩子结点，那么孩子结点的下标++，保证child下标一定是左右孩子最大值的下标
                child++;
            }
            //比较最大孩子结点与父亲结点的值，最大值放到父亲结点的位置。
            if (elem[child] > elem[parent]) {
                int tmp = elem[child];
                elem[child] = elem[parent];
                elem[parent] = tmp;
                parent = child;//交换完成之后，父节点指向其左孩子结点
                child = 2 * parent + 1;//child指向子树的孩子结点，通过循环，将子树建成堆
            } else {//如果最大孩子结点的值比父亲结点的值小，则直接结束。
                break;
            }
        }
    }

    //向上调整
    private void shiftUp(int[] elem,int child) {
        int parent = (child - 1) / 2;//利用孩子结点下标求父亲节点下标
        while (child > 0) {//当孩子结点的下标大于0时，进入循环，进行比较，交换
            if (elem[child] > elem[parent]) {//如果孩子结点的值比父亲结点的值大
                int tmp = elem[child];
                elem[child] = elem[parent];
                elem[parent] = tmp;
                child = parent;//交换完成之后，child指向父节点
                parent = (child - 1) / 2;//重新在计算父亲结点的下标，继续比较交换
            } else {//如果孩子结点没有父亲结点的值大，直接退出
                break;
            }
        }
    }

    //插入一个元素
    public void offer(int val) {
        if (isFull()) {//如果数组满了之后，则需要扩容
            elem = Arrays.copyOf(elem, 2 * elem.length);//对数组按照其长度的两倍进行扩容,将扩容后代结果用elem接收
        }
        elem[usedSize++] = val;//这里表示在数组的usedSize位置存放一个数据，存完之后数组长度+1
        shiftUp(elem,usedSize - 1);
    }

    //判断数组是否已满
    public boolean isFull() {
        return usedSize == elem.length;//当数组长度等于usedSize时，数组满了。因为在初始化数组时，给定了数组的长度
    }

    //删除堆顶元素
    public void pop() {
        if (isEmpty()) {//如果数组为空，则直接退出
            return;
        }
        swap(elem, 0, usedSize - 1);//若不为空，则调用交换方法，交换第一个元素和最后一个元素的位置
        usedSize--;//这里就相当于删除
        shiftDown(0, usedSize);//调用向下调整的方法，从0下标开始，调整usedSize个元素
    }

    //判断数组是否为空
    public boolean isEmpty() {
        return usedSize == 0;
    }

    //交换方法，给定一个数组，交换其i下标位置的数据和j下标位置的数据
    private void swap(int[] array, int i, int j) {
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }
    //找出数组中最大的k个数
    public int[] maxK(int[] arr, int k) {
        int[] ret = new int[k];//用来存放最终形成的前K个最大的值
        if (arr == null || k == 0) {
            return ret;
        }
        //创建堆，在堆内部的数组中，开辟k个空间
        Queue<Integer> minheap = new PriorityQueue<>(k);
        //遍历数组的前k个放入到堆中
        for (int i = 0; i < k; i++) {
            minheap.offer(arr[i]);//将传进来的数组元素放入到堆中
        }
        //假设数组长度为c
        //遍历剩下的c-k个，每次和堆顶元素进行比较
        for (int i = k; i < arr.length; i++) {
            if (arr[i] > minheap.peek()) {//比较堆顶元素和数组中剩余元素的大小
                minheap.poll();//弹出堆顶元素
                minheap.offer(arr[i]);//将数组中的元素放入堆中
            }
        }
        for (int i = 0; i < k; i++) {
            ret[i] = minheap.poll();//弹出堆顶元素，用ret数组接收
        }
        return ret;//最后将ret返回给调用者
    }
}



